{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上一篇我们学习了层次聚类。层次聚类只是迭代的把最相近的两个聚类匹配起来。\n",
    "\n",
    "并没有给出能给出多少的分组。\n",
    "\n",
    "今天我们来研究一个K均值聚类。就是给定分组数目的基础上再来聚类。即将所有的样本数据集分成K个组，每个组内尽可能相似，每个组间又尽可能不相似。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "k均值聚类和k中心点聚类属于基于划分的聚类。\n",
    "\n",
    "也就是给定了k值（簇的个数），我们通过不停的设计每个对象该属于哪个簇而实现聚类。\n",
    "\n",
    "我们今天使用k均值为文档进行分组。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K均值聚类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。\n",
    "\n",
    "该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。算法采用误差平方和准则函数作为聚类准则函数。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法过程如下：\n",
    "\n",
    "1）从N个文档随机选取K个文档作为质心\n",
    "\n",
    "2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类\n",
    "\n",
    "3）重新计算已经得到的各个类的质心\n",
    "\n",
    "4）迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "具体如下：\n",
    "\n",
    "输入：k, data;  其中data为n个样本集\n",
    "\n",
    "（1） 随机选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1]；\n",
    "\n",
    "（2） 对于data[0]….data[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；\n",
    "\n",
    "（3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数；\n",
    "\n",
    "（4） 重复(2)(3)，直到所有c[i]值的变化小于给定阈值。\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/b23dffdaec74ee623cb63667786f9b3f.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 案例实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 加载数据集\n",
    "\n",
    "\n",
    "使用我们一贯的文本数据集结构。每行为一个文档（链接或者文档名），每列为一个文档特征（单词），每个单元格的取值为单词在文档中出现的次数。\n",
    "\n",
    "[博客数据集点击下载](http://luanpeng.oss-cn-qingdao.aliyuncs.com/csdn/python/%E8%81%9A%E7%B1%BB/blogdata.txt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--2022-09-20 23:56:00--  http://luanpeng.oss-cn-qingdao.aliyuncs.com/csdn/python/%E8%81%9A%E7%B1%BB/blogdata.txt\n",
      "Resolving luanpeng.oss-cn-qingdao.aliyuncs.com (luanpeng.oss-cn-qingdao.aliyuncs.com)... 47.104.37.237\n",
      "Connecting to luanpeng.oss-cn-qingdao.aliyuncs.com (luanpeng.oss-cn-qingdao.aliyuncs.com)|47.104.37.237|:80... connected.\n",
      "HTTP request sent, awaiting response... 200 OK\n",
      "Length: 147123 (144K) [text/plain]\n",
      "Saving to: ‘blogdata.txt’\n",
      "\n",
      "blogdata.txt        100%[===================>] 143.67K  --.-KB/s    in 0.06s   \n",
      "\n",
      "2022-09-20 23:56:00 (2.25 MB/s) - ‘blogdata.txt’ saved [147123/147123]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "!wget http://luanpeng.oss-cn-qingdao.aliyuncs.com/csdn/python/%E8%81%9A%E7%B1%BB/blogdata.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Blog        china   kids    music   yahoo   want    ...\n",
    "Wonkette    0       2       1       0       6       ...\n",
    "Publishing  2       0       0       7       4       ...\n",
    "...         ...     ...     ...     ...     ...     ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "\n",
    "代码完成加载数据集，获取列名，行名，样本数据集\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 读取表格型数据，获取特征数据集。\n",
    "def readfile(filename):\n",
    "    lines=[line for line in open(filename)]\n",
    "\n",
    "    # 第一行是列标题\n",
    "    colnames=lines[0].strip().split('\\t')[1:]\n",
    "    rownames=[]\n",
    "    data=[]\n",
    "    for line in lines[1:]:\n",
    "        p=line.strip().split('\\t')\n",
    "        # 每行的第一列是行名\n",
    "        rownames.append(p[0])\n",
    "        # 剩余部分就是该行对应的数据\n",
    "        onerow = [float(x) for x in p[1:]]\n",
    "        data.append(onerow)\n",
    "    return rownames,colnames,data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 距离计算\n",
    "\n",
    "前面的文章我们已经了解了有欧式距离和皮尔逊相似度代表两个数组的亲密度。\n",
    "\n",
    "欧式距离计算简单，皮尔逊相似度稍微复杂些，不过在下面几种情况时效果好。\n",
    "\n",
    "1、在两个数组的尺度不相同，但是变化率相同时，效果好。比如，一个数组为[7,8,9]，一个数组为[1,2,3]其实这两种具有很强的相似度，只不过在尺度表现上不同罢了。\n",
    "\n",
    "2、在两个数组所具有的属性数目上不同时效果好。比如，一个数组为[1,5,9]和另一个数组[1,2,3,4,5,6,7,8,9]这两个数组也是具有很好的相似度的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在层次聚类中我们使用皮尔逊相似度来代替节点间距离。\n",
    "\n",
    "这是因为每个博客所拥有的特征属性的数目差距可能是很大的。\n",
    "\n",
    "皮尔逊的实现代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算两行的皮尔逊相似度\n",
    "def pearson(v1,v2):\n",
    "    # 简单求和\n",
    "    sum1=sum(v1)\n",
    "    sum2=sum(v2)\n",
    "\n",
    "    # 求平方和\n",
    "    sum1Sq=sum([pow(v,2) for v in v1])\n",
    "    sum2Sq=sum([pow(v,2) for v in v2])\n",
    "\n",
    "    # 求乘积之和\n",
    "    pSum=sum([v1[i]*v2[i] for i in range(len(v1))])\n",
    "\n",
    "    # 计算r\n",
    "    num=pSum-(sum1*sum2/len(v1))\n",
    "    den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))\n",
    "    if den==0: return 0\n",
    "\n",
    "    return 1.0-num/den"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意，在我们使用的博客数据集中，每个单元格的取值是单词在博客中出现的次数。\n",
    "不过在有些统计中，只关系单词是否在博客中出现，而不关系出现的次数。\n",
    "\n",
    "只要单词出现，则取值为1，单词不出现则取值为0。假如我们对同时希望拥有两件物品的人在物品方面互有重叠的情况进行度量。\n",
    "\n",
    "我们采用Tanimoto系数的度量方法，它代表的是交集与并集的比率。\n",
    "\n",
    "Tanimoto系数的计算实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用tanimoto系数表示距离（相似度）：两个向量的交集/两个向量的并集\n",
    "def tanamoto(v1,v2):\n",
    "    c1,c2,shr=0,0,0\n",
    "    for i in range(len(v1)):\n",
    "        if v1[i]!=0: c1+=1 # 出现在v1中\n",
    "        if v2[i]!=0: c2+=1 # 出现在v2中\n",
    "        if v1[i]!=0 and v2[i]!=0: shr+=1 # 在两个向量中都出现\n",
    "\n",
    "    return 1.0-(float(shr)/(c1+c2-shr))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 迭代实现k均值聚类\n",
    "\n",
    "\n",
    "随机设置k个聚类点，根据每个点到k个聚类点的距离，为每个点分组。移动聚类点到组成员中心位置。重新计算重新分组重新移动。迭代至成员不再变化。\n",
    "\n",
    "函数 返回k个聚类点，以及所包含的所有成员\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "# 每个点代表一行，每个聚类点，代表一类。参数：rows数据集，distance距离计算算法，k聚类的数目。\n",
    "def kcluster(rows,distance=pearson,k=4):\n",
    "    # 确定每个点的特征的最小值和最大值\n",
    "    ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))  for i in range(len(rows[0]))]\n",
    "\n",
    "    # 随机创建K个中心点\n",
    "    clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]\n",
    "               for i in range(len(rows[0]))] for j in range(k)]\n",
    "\n",
    "    lastmatches=None\n",
    "    for t in range(100):   #默认迭代100次。\n",
    "        print('迭代 %d' % t)\n",
    "        bestmatches=[[] for i in range(k)]  #生成k个空数组，用于存储k个聚类点包含的成员\n",
    "\n",
    "        # 在每一行中寻找距离最近的中心点\n",
    "        for j in range(len(rows)):\n",
    "            row=rows[j]\n",
    "            bestmatch=0\n",
    "            for i in range(k):\n",
    "                d=distance(clusters[i],row)\n",
    "                if d<distance(clusters[bestmatch],row): bestmatch=i   #计算与哪个聚类点最近\n",
    "            bestmatches[bestmatch].append(j)  #每个聚类点记录它包含的组成员\n",
    "\n",
    "        # 如果结果与上一次相同，则整个过程结束\n",
    "        if bestmatches==lastmatches: break\n",
    "        lastmatches=bestmatches\n",
    "\n",
    "        # 把中心点移动到成员的平均位置处\n",
    "        for i in range(k):\n",
    "            avgs=[0.0]*len(rows[0])\n",
    "            if len(bestmatches[i])>0:\n",
    "                for rowid in bestmatches[i]:\n",
    "                    for m in range(len(rows[rowid])):\n",
    "                        avgs[m]+=rows[rowid][m]\n",
    "                for j in range(len(avgs)):   #在每个维度都计算均值\n",
    "                    avgs[j]/=len(bestmatches[i])\n",
    "                clusters[i]=avgs\n",
    "\n",
    "    return bestmatches   #返回k个聚类点，以及所包含的所有成员"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 测试\n",
    "\n",
    "\n",
    "下面我们就可以来测试一下了。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "迭代 0\n",
      "迭代 1\n",
      "迭代 2\n",
      "迭代 3\n",
      "迭代 4\n",
      "['Mashable!', 'Slashdot', 'The Blotter', 'Schneier on Security', 'Signum sine tinnitu--by Guy Kawasaki', 'MetaFilter']\n"
     ]
    }
   ],
   "source": [
    "if __name__=='__main__':\n",
    "    from math import sqrt\n",
    "    blognames,words,data = readfile('blogdata.txt')  #加载数据集\n",
    "    kclust = kcluster(data,k=10)  #k均值聚类，形成k个聚类\n",
    "    print([blognames[r] for r in kclust[0]])  # 打印第一个聚类的所有博客名称"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输出结果\n",
    "\n",
    "```\n",
    "迭代 0\n",
    "\n",
    "迭代 1\n",
    "\n",
    "迭代 2\n",
    "\n",
    "迭代 3\n",
    "\n",
    "迭代 4\n",
    "\n",
    "[\"The Superficial - Because You're Ugly\", 'Joho the Blog', 'Go Fug Yourself', \"O'Reilly Radar\", 'Topix.net Weblog', 'flagrantdisregard', 'The Blotter', 'Schneier on Security']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到只迭代了5次就成功聚类完成。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# k-means聚类的优缺点：\n",
    "\n",
    " **k-means算法的优点：**\n",
    "\n",
    "（1）k-means算法是解决聚类问题的一种经典算法，算法简单、快速。\n",
    "\n",
    "（2）对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt)，其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常`k<<n`。这个算法通常局部收敛。\n",
    "\n",
    "（3）算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。\n",
    "\n",
    "**缺点：**\n",
    "\n",
    "（1）k-平均方法只有在簇的平均值被定义的情况下才能使用，且对有些分类属性的数据不适合。\n",
    "\n",
    "（2）要求用户必须事先给出要生成的簇的数目k。\n",
    "\n",
    "（3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。\n",
    "\n",
    "（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。\n",
    "\n",
    "（5）对于\"噪声\"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# k中心点算法\n",
    "\n",
    "\n",
    "k中心算法的基本过程是:\n",
    "\n",
    "首先为每个簇随意选择一个代表对象，剩余的对象根据其与每个代表对象的距离（此处距离不一定是欧氏距离，也可能是曼哈顿距离）分配给最近的代表对象所代表的簇；\n",
    "\n",
    "然后反复用非代表对象来代替代表对象，以优化聚类质量。\n",
    "\n",
    "聚类质量用一个代价函数来表示。当一个中心点被某个非中心点替代时，除了未被替换的中心点外，其余各点被重新分配。\n",
    "\n",
    "为了减轻k均值算法对孤立点的敏感性，k中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心。\n",
    "\n",
    "算法如下:\n",
    "\n",
    "输入:包含n个对象的数据库和簇数目k；\n",
    "\n",
    "输出:k个簇\n",
    "\n",
    "    （1）随机选择k个代表对象作为初始的中心点\n",
    "\n",
    "    （2）指派每个剩余对象给离它最近的中心点所代表的簇\n",
    "\n",
    "    （3）随机地选择一个非中心点对象y\n",
    "\n",
    "    （4）计算用y代替中心点x的总代价s\n",
    "\n",
    "    （5）如果s为负，则用可用y代替x，形成新的中心点\n",
    "    \n",
    "    （6）重复(2)(3)(4)(5)，直到k个中心点不再发生变化."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
